TOC-As-3

1. Construct NPDA’s that recognize the following languages over $\mathrm{\Sigma }=\{a,b,c\}$. (10 pt for each)

a. $L_2=\{a^n{b}^m{c}^{n+m}|n,m\ge 0\}$

b. $L_3=\{a^n{b}^{n+m}{c}^m|n,m\ge 0\}$

c. $L_4=\{a^3{b}^n{c}^n|n\ge 0\}$

2. Show that the language $\{a^n|n=2^{x}forallx\in \mathbb{N}\}$ is not contexr-free.

Let $L=\{a^n|n=2^{x}forallx\in \mathbb{N}\}$

Assume L is context-free.

Let $s=a^{2^p}$ which is a string in $L$.

And $s=wvxyz$

Suppose $w=a^i$, $v=a^j$,$x=a^k$,$y=a^l$,$z=a^m$ and $i+j+k+l+m=2^p$

By the pumping lemma,

$w{v}^{2}x{y}^{2}z=a^i{a}^{2j}{a}^k{a}^{2l}{a}^m$

Because $i+j+k+l+m=2^p$ and $j+l\ge 1$

Thus $j+l<i+j+k+l+m<i+2j+k+2l+m$

Therefore $i+2j+k+2l+m$ should at least be $2^{p+1}=2(i+j+k+l+m)$

Which means $j+l=i+j+k+l+m$ which is a contradiction.

Therefore $w{v}^{2}x{y}^{2}z$ is not in L.

Therefore L is not context-free.

3. Convert the following grammar to an NPDA. (8pt)

$$E\to E+E|id$$

4. Let $\mathrm{\Sigma }=\{a,b\}$. Design a (nondeterministic) TM for each following language. (10 pt each)

a. $\{a^n{b}^m|m\ge n\}$

b. $\{w|wisapalindrome\}$

c. $\{w|wisnotapalindrome\}$

d. $\{a^n|n=2^{x}forx\in \mathbb{N}\}$

5. Design a TM for each integer subtraction: $a-b$ for $a,b\in \mathbb{N}$. You need to clearly how the input and the side effect are encoded. (8pt each)

Let $\mathrm{\Gamma }=\{0,\mathrm{\#},-,x\}$

• Use 0 to represent positive numbers in the unary system.
• Use # as a separator between the two numbers.
• Use - as a special marker to indicate a negative result when $b>a$.
• Use x as a symbol to do the subtraction.

Input Format

• The first part of the tape will consist of a sequence of 0s representing $a$.
• The second part, after the separator #, will contain a sequence of 10s representing $b$.

For example:

• 000#00 represents $3-2$, should be output as 0 (positive result).
• 00#000 represents $2-3$, and should be output as -0 (negative result).

6. Let $\mathrm{\Gamma }=\{a,b,\bigsqcup \}$ Design a $TM$ which decides whether the symbol $b$ is on the tape. (8pt)